package com.zhj.leetcode;

import java.util.*;

/**
 * 力扣128
 * 最长连续序列
 * @author zhj
 * @create 2024-02-18-10:51
 */
public class Test128 {
    public static void main(String[] args) {
        int[] nums = new int[]{100,4,200,1,3,2};
        System.out.println(longestConsecutive2(nums));
    }

    public static int longestConsecutive1(int[] nums) {
        int r = 0;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        for (int num : set) {
            int ans = 0;
            if (!set.contains(num-1)) {
                while (set.contains(num++)) {
                    ans++;
                }
                r = Math.max(r, ans);
            }
        }
        return r;
    }

    public static int longestConsecutive2(int[] nums) {
        int r = 0;
        UnionFind uf = new UnionFind(nums);
        for (int num : nums) {
            if (uf.find(num + 1) != null) {
                uf.union(num, num+1);
            }
        }
        for (int num : nums) {
            int right = uf.find(num);
            r = Math.max(r, right -num + 1);
        }
        return r;
    }

    static class UnionFind {
        // 记录每个节点的父节点
        private Map<Integer, Integer> parent;

        public UnionFind(int[] nums) {
            parent = new HashMap<>();
            // 初始化父节点为自身
            for (int num : nums) {
                parent.put(num, num);
            }
        }

        // 寻找x的父节点，实际上也就是x的最远连续右边界，这点类似于方法2
        public Integer find(int x) {
            // nums不包含x
            if (!parent.containsKey(x)) {
                return null;
            }
            // 遍历找到x的父节点
            while (x != parent.get(x)) {
                // 进行路径压缩，不写下面这行也可以，但是时间会慢些
                parent.put(x, parent.get(parent.get(x)));
                x = parent.get(x);
            }
            return x;
        }

        // 合并两个连通分量，在本题中只用来将num并入到num+1的连续区间中
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            parent.put(rootX, rootY);
        }
    }
}
